/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-05-26
 * Time: 10:02
 */
class Solution10 {
    public int profitableSchemes(int n, int m, int[] group, int[] profit) {
        int len = group.length,MOD = (int)1e9+7;

        int[][][] dp = new int[len+1][n+1][m+1];

        for(int j = 0; j <= n; j++) {
            dp[0][j][0] = 1;
        }

        for(int i = 1; i <= len; i++) {
            for(int j = 0; j <= n; j++) {
                for(int k = 0; k <= m; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j >= group[i-1]) {
                        dp[i][j][k] += dp[i-1][j-group[i-1]][Math.max(0,k-profit[i-1])];
                        dp[i][j][k] %= MOD;
                    }
                }
            }
        }
        return dp[len][n][m];
    }
}

//优化后
//class Solution {
//    public int profitableSchemes(int n, int m, int[] group, int[] profit) {
//        int len = group.length,MOD = (int)1e9+7;
//
//        int[][] dp = new int[n+1][m+1];
//
//        for(int j = 0; j <= n; j++) {
//            dp[j][0] = 1;
//        }
//
//        for(int i = 1; i <= len; i++) {
//            for(int j = n; j >= group[i-1]; j--) {
//                for(int k = m; k >= 0; k--) {
//                    dp[j][k] += dp[j-group[i-1]][Math.max(0,k-profit[i-1])];
//                    dp[j][k] %= MOD;
//                }
//            }
//        }
//        return dp[n][m];
//    }
//}
